In general, in many communication devices and recording and reproducing devices, reduction in the BER of digital transmission information is attempted by transmitting a code sequence arising from coding of an input information sequence.
FIG. 1 is a block diagram showing the configuration of a conventional wireless communication system 1 composed of a transmitting device 11 and a receiving device 12.
In FIG. 1, initially an information sequence on the user side is input to a coder 21 and is coded at a rate of k/n to become a code sequence.
Here, k is the information word length, n is the codeword length, and k/n is called the code rate or the coding rate. Furthermore, for the coding, plural kinds of coding, such as encryption, error correction coding, and RLL (run length limited) coding, are frequently combined.
The code sequence is input to a transmitter 22, and transmission signals are transmitted to the space by a transmitting antenna in the transmitter 22 in the case of the transmitting device 11 in the wireless communication system 1.
The transmission signals are input to a receiver 31, and the input signals are converted from the signals in the space to analog reception signals by a receiving antenna in the receiver 31 in the case of the receiving device 12 in the wireless communication system 1.
These analog signals are equalized to a predetermined target equalization characteristic by using an analog equalizer, which is not diagrammatically represented, and then converted every time to digital reception signals in an A/D (analog/digital) converter 32. A phase synchronization circuit, which is not diagrammatically represented, is included in the A/D converter 32.
The digital reception signals are converted to a detected code sequence or a sequence of information on the posterior probability thereof in a code detector 33, and thereafter input to a decoder 34, followed by being decoded to detected information words at a rate of n/k to become a detected information sequence.
However, if the equalization by the analog equalizer is not sufficient, there is also a case in which a digital equalizer is provided between the A/D converter 32 and the code detector 33. Furthermore, in recent years, it is general that a soft-decision detector such as a Viterbi detector is used in the code detector 33. Moreover, if an iterative decoding method is used in the decoder 34, a posterior probability detector is used in the code detector 33 in some cases.
Although the wireless communication system 1 composed of the transmitting device 11 and the receiving device 12 is described in FIG. 1, it is also possible to employ a recording and reproducing system composed of a recording device in which a recorder is provided instead of the transmitter 22 and a reproducing device in which a reproducer is provided instead of the receiver 31. In this case, the processing executed by the coder 21, the A/D converter 32, the code detector 33, and the decoder 34 in the recording and reproducing system is similar to the processing executed in the wireless communication system 1.
By the way, in FIG. 1, various codes are studied as the error correcting codes used in the coder 21 and the decoder 34, and a part of the codes, such as an RS (Reed Solomon) code, has been put into practical use.
In recent years, studies are being intensively promoted on e.g. communication fields such as mobile communication and deep space communication and broadcasting fields such as terrestrial or satellite digital broadcasting. Along with this, studies relating to the code theory for the purpose of enhancing the efficiency in the error correction coding and decoding are also being made.
As a theoretical limit to the code performance, the Shannon limit, given by the so-called channel coding theory of Shannon (C. E. Shannon), is known. One of the purposes of the studies relating to the code theory is to develop codes exhibiting performance close to this Shannon limit. As coding methods exhibiting performance close to the Shannon limit, schemes referred to as so-called turbo coding, such as parallel concatenated convolutional codes and serial concatenated convolutional codes, have been developed.
Furthermore, in recent years, while these turbo codes are developed, studies are being actively made on a low-density parity-check (LDPC (low-density parity-check code) code as one of error correcting codes that are used by the coder 21 and the decoder 34 in FIG. 1 and are effective to reduce the BER of transmission information.
Although the LDPC code was a code that was proposed in 1962 by R. G. Gallager and had been known from old times, recently it is becoming clear that the LDPC code has very excellent decoding performance. The LDPC code is disclosed in Non-patent document 1. Due to recent studies, it is becoming known that, in the case of a code having a low code rate, the LDPC code can achieve performance closer to the Shannon limit when the code length is set longer. Furthermore, the LDPC code has a characteristic that the minimum distance is not necessarily in proportion to the code length.
Here, the LDPC code refers to a parity check code having a parity check matrix (hereinafter, referred to as the check matrix) in which the density of non-zero elements is low (sparse).
Therefore, the LDPC code is the name applied to codes in a very wide range for which the number of non-zero elements in the check matrix is only defined somewhat ambiguously, and does not refer to a code that follows a certain specific code generation rule unlike e.g. the RS code, which is generally well-known. That is, attention needs to be paid to the fact that there exist infinitely many codes that can be called the LDPC code.
Furthermore, in general, one of iterative decoding methods called a Sum-Product decoding method or a Belief-Propagation (BP) decoding method is applied to decoding of the LDPC code.
In the LDPC code, such a code that the column weight of the check matrix is constant is called a regular LDPC code, whereas such an LDPC code that the column weight of the check matrix is not constant is called an irregular LDPC code.
Compared with the regular LDPC code, the irregular LDPC code can achieve higher error correction ability generally but readily leads to a larger circuit scale. However, when the code rate is higher, the difference in the error correction ability between the irregular LDPC code and the regular LDPC code is smaller.
Furthermore, in recent years, a method in which a QC (Quasi Cyclic) code known from old times is used as the LDPC code is attracting attention as one of methods that can reduce the circuit scales of coder and decoder for the LDPC code (in FIG. 1, the coder 21 and the decoder 34).
The regularity of the check matrix of the QC code is very high, and it is expected that, when the QC code is used as the LDPC code, the circuit scales of coder and decoder can be reduced by utilizing the regularity.
Here, the QC code refers to a code in which a sequence arising from the cyclic shift of any codeword by a cycle p (1≦p<n) that is a certain natural number is a codeword other than the original codeword. The QC code with p=1 is called the cyclic code.
Details of the QC code are disclosed in e.g. Non-patent document 2. The check matrix of the QC code can be represented by using p·q cyclic matrices, in which q is a natural number.
In general, an m rows and m columns (m×m) cyclic matrix is defined as a matrix in which all columns arise from the cyclic shift of any certain column such as the first column.
Specifically, if the leftmost first column vector in an m×m cyclic matrix C is defined as [x0x1 . . . xm−1]T (T represents transposition operation), C is represented as the following Equation (1).
                    [                  Formula          ⁢                                          ⁢          1                ]                                                            C        =                  (                                                                      x                  0                                                                              x                                      m                    -                    1                                                                                                x                                      m                    -                    2                                                                              …                                                              x                  1                                                                                                      x                  1                                                                              x                  0                                                                              x                                      m                    -                    1                                                                              …                                                              x                  2                                                                                                      x                  2                                                                              x                  1                                                                              x                  0                                                            …                                                              x                  3                                                                                    ⋮                                            ⋮                                            ⋮                                            ⋱                                            ⋮                                                                                      x                                      m                    -                    1                                                                                                x                                      m                    -                    2                                                                                                x                                      m                    -                    3                                                                              …                                                              x                  0                                                              )                                    (        1        )            
Although the respective columns of the cyclic matrix C are cyclically shifted in the downward direction of the matrix in Equation (1), the cyclic matrix C may be defined by cyclically shifting them in the upward direction. The inverse matrix of a cyclic matrix and the product of two cyclic matrices are each a cyclic matrix.
A check matrix H(p, q) of a QC code, composed of p·q cyclic matrices and having a cycle p, is defined as the following Equation (2) in general.
                    [                  Formula          ⁢                                          ⁢          2                ]                                                                      H          ⁡                      (                          p              ,              q                        )                          =                  (                                                                      D                                      0                    ,                    0                                                                                                D                                      0                    ,                    1                                                                              …                                                              D                                      0                    ,                                          m                      -                      1                                                                                                                                            D                                      1                    ,                    0                                                                                                D                                      1                    ,                    1                                                                              …                                                              D                                      1                    ,                                          m                      -                      1                                                                                                                          ⋮                                            ⋮                                            ⋱                                            ⋮                                                                                      D                                                            q                      -                      1                                        ,                    0                                                                                                D                                                            q                      -                      1                                        ,                    1                                                                              …                                                              D                                                            q                      -                      1                                        ,                                          m                      -                      1                                                                                                    )                                    (        2        )            
Here, in Equation (2), Di,h is an m×p matrix whose j-th column is the h-th column (0≦h<m) of an m×m cyclic matrix Ci,j in a matrix H′(p, q) of the following Equation (3), arising from rearrangement of the columns in H(p, q).
                    [                  Formula          ⁢                                          ⁢          3                ]                                                                                  H            ′                    ⁡                      (                          p              ,              q                        )                          =                  (                                                                      C                                      0                    ,                    0                                                                                                C                                      0                    ,                    1                                                                              …                                                              C                                      0                    ,                                          p                      -                      1                                                                                                                                            C                                      1                    ,                    0                                                                                                C                                      1                    ,                    1                                                                              …                                                              C                                      1                    ,                                          p                      -                      1                                                                                                                          ⋮                                            ⋮                                            ⋱                                            ⋮                                                                                      C                                                            q                      -                      1                                        ,                    0                                                                                                C                                                            q                      -                      1                                        ,                    1                                                                              …                                                              C                                                            q                      -                      1                                        ,                                          p                      -                      1                                                                                                    )                                    (        3        )            
Because Equation (3) arises from only rearrangement of the columns of Equation (2), the decoding performance for a reception signal having white noise is the same whichever check matrix the code has. Therefore, hereinafter, no distinction is made between the check matrix having the form of Equation (2) and the check matrix having the form of Equation (3) unless a particular notice is made.
The column weight wc of the respective cyclic matrices in such a check matrix of a QC code is any integer equal to or larger than zero, and the respective cyclic matrices may have different column weights. However, in general, only a method for designing a check matrix in which q=1 and wc≧2 and wc is constant and a method for designing a check matrix in which q≧2 and wc belongs to {0, 1} have been known so far as a specific method for designing a check matrix.
A specific method for designing a check matrix in which q=1 and wc≧2 is disclosed in e.g. Non-patent document 3 and Non-patent document 4 proposed by the present inventor.
Furthermore, a specific method for designing a check matrix in which q≧2 and wc belongs to {0, 1} is disclosed in e.g. Non-patent document 5.
If a check matrix in which q≧2 and wc belongs to {0, 1} is used, there is an advantage that both a regular LDPC code and an irregular LDPC code can be designed comparatively easily.
In addition, if the code length is somewhat long and the code rate is low, employing the relationship w, belongs to {0, 1} also provides an advantage that low-error-rate performance is obtained easily when the code is used as an LDPC code because a short cycle hardly occurs on the check matrix.
On the other hand, as pointed out also in Non-patent document 4, a self-orthogonal QC code having a higher code rate can be designed when a check matrix in which q=1 and wc≧2 is used than when a check matrix in which q≧2 and wc belongs to {0, 1} is used, if the code length is the same. It is generally known that, if the code is self-orthogonal, a cycle with a length of 4 does not exist in the check matrix thereof and the decoding performance thereof can be improved when it is used as an LDPC code.
Coding of a QC code can be carried out by using a very simple shift register circuit. The method therefor is disclosed in e.g. the above-mentioned Non-patent document 2, Patent document 1, and Patent document 2.
Furthermore, as one of methods by which a simple coding circuit can be formed not only for the QC code, a method in which a lower triangular form or a dual diagonal form is made in a part of the check matrix has also been proposed, and details thereof are disclosed in e.g. Non-patent document 6. If this method is used, the code does not necessarily need to be a QC code.
By the way, generally in a wireless communication device (in FIG. 1, the wireless communication system 1), plural error correcting codes having different code rates are prepared and one of them is selected and used depending on the condition of the transmission path in many cases.
In this case, if different coders and decoders (in FIG. 1, the coder 21 and the decoder 34) are provided for all of the codes, the circuit scale often becomes large. Therefore, it is desirable that the circuit of these plural coders and decoders is shared as much as possible. The code that is so designed that the circuit is shared by plural codes having different code rates as much as possible is generally called a Rate-Compatible code.
Also for the LDPC code, various studies to design the Rate-Compatible LDPC (hereinafter, referred to as the RC-LDPC) code are being made in recent years.
For the RC-LDPC code, a scheme in which the check matrix of certain one original code (mother code) is transformed or used as it is to prepare check matrices of codes having other code rates is general. For the RC-LDPC codes reported so far, the check matrices thereof have a form in which q≧2 and wc belongs to {0, 1} in Equation (2) in many cases, and the content thereof is disclosed in e.g. Non-Patent document 7, Non-patent document 8, and Patent document 3.
Many methods for constructing the RC-LDPC code utilize techniques of puncturing and shortening, which are conventionally well-known in the code theory, and e.g. the method of Non-patent document 7 also utilizes the puncturing.
On the other hand, proposed in Non-patent document 8 and Patent document 3 is a method in which the check matrix of a code having a low code rate is obtained by performing dividing (splitting) of each row in the check matrix of the mother code having a high code rate for each cyclic matrix.
FIG. 2 is a diagram for explaining the row splitting performed in some cyclic matrices in the check matrix, disclosed in Non-patent document 8.
In FIG. 2, by regarding 0 as a zero matrix and regarding 1 as a cyclic matrix of wc=1, the way in which cyclic matrices are split into plural stages in a check matrix in which q≧2 and wc belongs to {0, 1} is expressed. Furthermore, although what the cyclic matrix of wc=1 is specifically is not diagrammatically represented in FIG. 2, attention needs to be paid to the point that all of the respective cyclic matrices after the splitting except for the zero matrix are formed of the same cyclic matrices as the cyclic matrices before the splitting.
If the number of rows in the check matrix before the splitting is defined as m1, the number of rows in the check matrix after the splitting becomes 2 m1 through splitting of cyclic matrices into two stages like in FIG. 2. Now, if it is assumed that the check matrix is full rank, i.e. the number of rows in the check matrix is equal to the parity number, the code rate of the code having the check matrix before the splitting is (n−m1)/n, and the code rate of the code having the check matrix resulting from the splitting of each row into two stages is (n−2 m1)/n.
If plural check matrices are made by repeatedly performing such cyclic matrix splitting, sharing of the decoding circuit is permitted because the basic form of these check matrices is the same.
The coding and decoding are possible wherever the positions of the parity on the check matrix are. However, in an actual system, because of easiness in terms of the system configuration, it is desirable that the positions of the parity exist with constant intervals on the check matrix or are collectively arranged on the right side or the left side on the check matrix.
However, if plural check matrices are made by performing row splitting like in FIG. 2, it is not necessarily easy to dispose parity at the desired positions on the check matrix for all of the check matrices. Therefore, in Non-patent document 8, each check matrix has a dual diagonal form like that disclosed in Non-patent document 7 in order to arrange parity on the right side of the check matrix. Consequently, the row splitting like in FIG. 2 can not be performed for the parity part, and the regularity thereof is broken.
The method of Patent document 3 is also a method in which splitting is performed in the row direction for each cyclic matrix similarly to the method of Non-patent document 8. However, a specific coding method is not shown in the method disclosed in Patent document 3 although row splitting of the check matrix like that shown in FIG. 2 is performed, including the parity part. For example, in the code disclosed in Patent document 3, the parity part irregularly exists on the check matrix.
Thus, also in Patent document 3, the possibility that a form such as a dual diagonal form must be combined in order to form a practical coder is pointed out. However, in this case, the regularity of the parity part is broken similarly to the case of Non-patent document 8.    Patent document 1: U.S. Pat. No. 3,475,724    Patent document 2: U.S. Pat. No. 6,928,602    Patent document 3: I. Rakkis, “System and Methods for a Turbo Low-density Parity-check Decoder,” United States Patent Application Publication, US2007/0043998 A1, Feb. 2007.    Non-patent document 1: R. G. Gallager, “Low Density Parity Check Codes,” MIT Press, Cambridge, Mass., 1963.    Non-patent document 2: R. Townsend and E. Weldon, Jr., “Self-Orthogonal Quasi-Cyclic Codes,” IEEE Trans. Info. Theory, vol. IT-13, no. 2, pp. 183-195, Apr. 1967.    Non-patent document 3: Y. Kou, S. Lin and M. Fossorier, “Low Density Parity Check Codes on Finite Geometries: A Rediscovery and New Results,” IEEE Trans. Info. Theory, vol. 47, no. 7, pp. 2711-2735, Nov. 2001.    Non-patent document 4: M. Noda, “Designing a Self-orthogonal Quasi-cyclic Code with Extended Minimum Hamming Distance,” Proc. 4th International Symposium on Turbo Code and Related Topics, Munich, Germany, Apr. 2006.    Non-patent document 5: M. Fossorier, “Quasi-cyclic Low-density Parity-check Codes From Circulant Permutation Matrices,” IEEE Trans. Info. Theory, Vol. 50, No. 8, pp. 1788 1793, Aug. 2004.    Non-patent document 6: T. J. Richardson and R. L. Urbanke, “Efficient Encoding of Low-density Parity-check Codes,” IEEE Trans. Info. Theory, Vol. 47, No. 2, pp. 638 656, Feb. 2001.    Non-patent document 7: D. Klinc, J. Ha, J. Kim and S. W. McLaughlin, “Rate-compatible Punctured Low-density Parity-check Codes for Ultra Wide Band System,” Proc. IEEE (GLOBECOM 2005), pp. 3856 3860.    Non-patent document 8: H-G. Joo, D-J Shin and S-N. Hong, “New Construction of Rate-compatible Block-type Low-density Parity-check Codes using Splitting,” Proc. IEEE (PIMRC 2006). Sep. 2006